package nachos.threads;
import nachos.machine.*;
import java.util.LinkedList;

/**
  An implementation of condition variables built upon semaphores.
 
  A condition variable is a synchronization primitive that does not have
  a value (unlike a semaphore or a lock), but threads may still be queued.
 
  sleep(): atomically release the lock and relinkquish the CPU
  until woken; then reacquire the lock.
 
  wake(): wake up a single thread sleeping in this condition
  variable, if possible.
 
  wakeAll(): wake up all threads sleeping inn this condition variable.
 
  Every condition variable is associated with some lock. Multiple condition
  variables may be associated with the same lock. All three condition variable
  operations can only be used while holding the associated lock.
 
  In Nachos, condition variables are summed to obey Mesa-style
  semantics. When a wake() or wakeAll() wakes up another
  thread, the woken thread is simply put on the ready list, and it is the
  responsibility of the woken thread to reacquire the lock (this reacquire is
  taken care of in sleep()).
 
  By contrast, some implementations of condition variables obey
  Hoare-style semantics, where the thread that calls wake()
  gives up the lock and the CPU to the woken thread, which runs immediately
  and gives the lock and CPU back to the waker when the woken thread exits the
  critical section.
 
  The consequence of using Mesa-style semantics is that some other thread
  can acquire the lock and change data structures, before the woken thread
  gets a chance to run. The advance to Mesa-style semantics is that it is a
  lot easier to implement.
*/
public class Condition 
{
    /**
      Allocate a new condition variable.
     
      Parameters:
		conditionLock - the lock associated with this condition
						variable. The current thread must hold this
						lock whenever it uses sleep(),
						wake(), or wakeAll().
    */
    public Condition(Lock conditionLock) 
	{
		this.conditionLock = conditionLock;
		waitQueue = new LinkedList<Semaphore>();
    }

    /**
      Atomically release the associated lock and go to sleep on this condition
      variable until another thread wakes it using wake(). The
      current thread must hold the associated lock. The thread will
      automatically reacquire the lock before sleep() returns.
     
      This implementation uses semaphores to implement this, by allocating a
      semaphore for each waiting thread. The waker will V() this
      semaphore, so thre is no chance the sleeper will miss the wake-up, even
      though the lock is released before caling P().
    */
    public void sleep() 
	{
		Lib.assertTrue(conditionLock.isHeldByCurrentThread());

		Semaphore waiter = new Semaphore(0);
		waitQueue.add(waiter);																//Adds a semaphore to the wait queue

		conditionLock.release();
		waiter.P();																			//Calls P() in the semaphore... What is P()???
		conditionLock.acquire();																		
    }

    /**
      Wake up at most one thread sleeping on this condition variable. The
      current thread must hold the associated lock.
    */
    public void wake() 
	{
		Lib.assertTrue(conditionLock.isHeldByCurrentThread());

		if (!waitQueue.isEmpty())
			((Semaphore) waitQueue.removeFirst()).V();										//Calls V() on the first semaphore in the wait list... What is V()
    }

    /**
      Wake up all threads sleeping on this condition variable. The current
      thread must hold the associated lock.
    */
    public void wakeAll() 
	{
		Lib.assertTrue(conditionLock.isHeldByCurrentThread());

		while (!waitQueue.isEmpty())
			wake();
    }

    private Lock conditionLock;
    private LinkedList<Semaphore> waitQueue;
}
